package a_12届蓝桥真题;

import java.util.Scanner;

/*
					1
				1		1
			1		2		1
		1		3		3		1
	1		4		6		4		1
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入格式
输入一个整数 N

输出格式
输出一个整数代表答案

数据范围
对于 20%的评测用例，1≤N≤10；
对于所有评测用例，1≤N≤10e9

输入样例：
6

输出样例：
13

 */
public class h杨辉三角test {
	public static void main(String[] args) {
		h杨辉三角test test = new h杨辉三角test();
		test.useDeal();
//		double res = test.getNumberOfCombinations1(6, 3);
//		System.out.println(res);
	}
	
	public double getNumberOfCombinations1(int down, int up) {
		double a = 1;
		double b = 1;
		double temp = 1;
		for (int i = 1; i < down + 1; i++) {
			a = a * i;
		}
		for (int i = 1; i < up + 1; i++) {
			b = b * i;
		}
		for (int i = 1; i < down - up + 1; i++) {
			temp = temp * i;
		}
		return a / (b * temp);
	}
	
	/**
	 * 我们设，从右上到左下，是行row；从左上到右下，是列col；以金字塔视角，从左到右，是行k。
	 * 杨辉三角从每行开始的中间数的值 = C(2n, n)，n是行数，从0开始
	 * 这里的C()方法就是我写的getNumberOfCombinations()，所以要注意参数的顺序
	 * n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行n即可！
	 * C(32, 16) < 1e9,肯定存在一部分没考虑到。不过没事，我们可以顺着16行，继续沿左下找！
	 */
	public void useDeal() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		for (int n = 1;; n--) {
			if (deal(N, n)) {
				break;
			}
		}
	}
	
	/**
	 * 斜行的二分查找
	 * @param N
	 * @param n
	 * @return
	 */
	public boolean deal(int N, int n) {
		int l = 2 * n;
		int r = Math.max(N, l);
		while (l < r) {
			int mid = l + r >>> 1;
			double test = getNumberOfCombinations(mid, n, N);
			if (getNumberOfCombinations(mid, n, N) >= N) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		if (getNumberOfCombinations(r, n, N) != N) {
			return false;
		}
		System.out.println(1D * (r + 1) * r / 2 + n + 1);//找到N这个数的位置了！
		return true;//返true，终结循环
	}
	
	/**
	 * 求组合数
	 * ---b
	 * |
	 * ---a
	 * a! / (b! * (a - b)!)
	 * 
	 * ---up
	 * |
	 * ---down
	 * @param down
	 * @param up
	 * @return
	 */
	public double getNumberOfCombinations(int down, int up, int N) {
		double res = 1;
		for (int i = down, j = 1; j <= up; i--, j++) {
			res = res * i / j;
			if (res > N) {// 大于N已无意义，且防止爆double
				return res;
			}
		}
		return res;
	}
}
